\section{Recursive Best-First Search}

Recursive best-first search or RBFS works by storing an f-limit variable to keep track of the f-value of the best alternative path available from any ancestor node to the current node. The algorithm uses the f-limit to decide which subtree of the problem tree to explore by considering the current path and the best alternative path. In order to keep the search functional, RBFS also updates the f-values of each node during the recursion unwinding. This allows RBFS to consider the forgotten subtree in the future.

The advantage of RBFS over A* is that RBFS uses less memory, linear space. Whereas A* stores all of its explored nodes, RBFS will only keep ``relevant'' nodes in memory. However, the disadvantage of RBFS over A* is that RBFS could expand more nodes than A* due to redundancy. Since RBFS does not store all nodes explored, it can re-expand the same nodes and thereby increasing computation time.

The pseudocode is listed in algorithm \ref{alg2}.

\begin{algorithm}
\caption{RBFS Search}
\label{alg2}
\begin{algorithmic}
\STATE function RBFS(state, f-limit):
\IF{state is goal state}
	\RETURN solution
\ENDIF
\STATE successor = all children of state
\IF{successors is empty}
	\RETURN failure
\ELSE
	\FOR{s in successors}
		\STATE s.$f$ = $max$(s.$g$ + s.$h$, state.$f$)
	\ENDFOR
	\WHILE{\TRUE}
		\STATE best = lowest f-value node in successors
		\IF{best.$f$ $>$ f-limit}
			\RETURN failure, best.$f$
		\ENDIF
		\STATE alternative = second best f-value of any node in successors
		\STATE result, best.$f$ = RBFS(best, $min$(f-limit, alternative))
		\IF{result is not failure}
			\RETURN result
		\ENDIF
	\ENDWHILE
\ENDIF
\end{algorithmic}
\end{algorithm}

%We will analyze several admissble and non-admissble heuristics in section \ref{sec:exp}.

%\begin{table}[h]
%    \centering
%    \begin{tabular}{|l|l|l|c|c|c|c|c|}
%        \hline
%        WALL & DIRT & HOME & FORWARD & RIGHT & LEFT & SUCK & OFF  \\ \hline
%        1    & 0    & 1    & 0.0     & 0.65  & 0.33 & 0.0  & 0.02 \\ 
%        1    & 1    & 0    & 0.0     & 0.0   & 0.0  & 1.0  & 0.0  \\ 
%        1    & 1    & 1    & 0.0     & 0.0   & 0.0  & 1.0  & 0.0  \\ 
%        1    & 0    & 0    & 0.0     & 0.67  & 0.33 & 0.0  & 0.0  \\ 
%        0    & 0    & 1    & 0.9     & 0.05  & 0.05 & 0.0  & 0.0  \\ 
%        0    & 1    & 0    & 0.0     & 0.0   & 0.0  & 1.0  & 0.0  \\ 
%        0    & 1    & 1    & 0.0     & 0.0   & 0.0  & 1.0  & 0.0  \\ 
%        0    & 0    & 0    & 0.8     & 0.1   & 0.1  & 0.0  & 0.0  \\
%        \hline
%    \end{tabular}
%    \caption{Parameters of multinomial distributions for each situation.}\label{tab:random}
%\end{table}
